package com.leetcode.search;

/**
 * leetcode 130 被围绕的区域
 */
public class Solution130 {
    public void solve(char[][] board) {
        if (board == null) {
            return;
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (isBorderO(board, i, j)) {
                    dfs(board, i, j);
                }
            }
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    private void dfs(char[][] board, int row, int column) {
        if (row < 0 || row >= board.length
                || column < 0 || column >= board[row].length
                || board[row][column] == 'X'
                || board[row][column] == '#') {
            return;
        }

        board[row][column] = '#';
        // 上
        dfs(board, row - 1, column);
        // 下
        dfs(board, row + 1, column);
        // 左
        dfs(board, row, column - 1);
        // 右
        dfs(board, row, column + 1);
    }

    private boolean isBorderO(char[][] board, int row, int column) {
        if ((row == 0 || row == board.length - 1 || column == 0 || column == board[row].length - 1)
                && board[row][column] == 'O') {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Solution130 solution130 = new Solution130();
        char[][] board = new char[][]{
                {'O', 'X', 'X', 'O', 'X'},
                {'X', 'O', 'O', 'X', 'O'},
                {'X', 'O', 'X', 'O', 'X'},
                {'O', 'X', 'O', 'O', 'O'},
                {'X', 'X', 'O', 'X', 'O'}};
        solution130.solve(board);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }
}
